Introduction

Nous souhaitons réalisé l’étude d’une série temporelle et faire des prévisions sur celle-ci.

Cette série temporelle est le trafic mensuel d’une Compagnie aérienne de janvier 2011 à août 2019.

Nos prévisions portent sur les 8 mois de l’année 2019

Représentation graphique de la série.

Import des données

Import de la base, on sélectionne la colonne des valeurs

library(readr)
data <- read_delim("Trafic-voyageurs.csv", 
    delim = ";", locale = locale(encoding = "ISO-8859-1"))
Rows: 104 Columns: 2
── Column specification ───────────────────────────────────────────────────────────────────────────────────────────────
Delimiter: ";"
chr (1): dates
dbl (1): trafic

ℹ Use `spec()` to retrieve the full column specification for this data.
ℹ Specify the column types or set `show_col_types = FALSE` to quiet this message.
summary(data)
    dates               trafic      
 Length:104         Min.   :220876  
 Class :character   1st Qu.:297154  
 Mode  :character   Median :355178  
                    Mean   :354651  
                    3rd Qu.:407331  
                    Max.   :505190  
data_value <- data[,2]

Affichage

Création de la série chronologique :

library(TSstudio)
data_ts <- ts(data_value, start=2011, frequency=12)
plot_1_TimeSeries(data_ts)

Séparation jeu de données

#revoir l affichage car ca prend pas en compte tt 2019
data_ts_train <- window(data_ts, start = c(2011, 1), end = c(2018,12))
data_ts_test <- window(data_ts, start= c(2019,1), end = c(2019,8))

plot(data_ts, xlim=c(2011,2020))
lines(data_ts_test, col=3)
legend("topleft", lty = 1, col=c(1,3), legend=c("Série chronologique Train", "Série chronologique Test"))

-> strong trend -> patern qui se repete, saisonnalité ?

Représentation de la saisonnalité

Analyse de la saisonnalité en superposant chaque année (par mois):

-> en supprimant la tendance on voit bien la saisonnalité => saisonnalité régulière

ggseasonplot(data_ts)

data_ts_without_trend = diff(data_ts)
ggseasonplot(data_ts_without_trend)

Représentation des décompositions possibles

DECOMPOSITION : additive / Multiplicative Ts = Trend + Seasonal + Random / Ts = Trend * Seasonal * Random

decomposed_data <- decompose(data_ts_train, type="additive")
plot(decomposed_data$trend)

plot(decomposed_data$seasonal)

plot(decomposed_data$random)


boxplot(data_ts ~ cycle(data_ts))

-> on distingue des saisonnalités => faire régression ca n’a pas de sens => modèle de Buys Ballot

-> bonne repartition du bruit -> quelques outliers

checkresiduals(remainder(decomposed_data))
Warning in modeldf.default(object) :
  Could not find appropriate degrees of freedom for this model.

On a tendances + saisonnalité

Modèles espace-état

  • meanf : Average Method : prend la valeur moyenne de toute les observations pour toutes les prédictions,
  • naive : Naive Method : prend la dernière observation pour toutes les prédictions,
  • drift : Drift Method : prend la première et la dernière observations et trace une lignes entre les deux, on utilise la courbe pour les prédictions,
  • snaive : Seasonal Naive Forecast : Prend la dernière valeur de la saison précédente comme prédiction (ex : sept 2018 = sep 2019 + erreur)
library(forecast)
mean <- meanf(data_ts_train, h=8)
naivem <- naive(data_ts_train, h=8)
driftm <- rwf(data_ts_train, h=8, drif=T)
snaivem <- snaive(data_ts_train, h=8)
plot(mean, plot.conf = F, main="")
Warning in plot.window(xlim, ylim, log, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in title(main = main, xlab = xlab, ylab = ylab, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in axis(1, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in axis(2, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in box(...) : "plot.conf" n'est pas un paramètre graphique
lines(naivem$mean, col=2, lty=1)
lines(driftm$mean, col=5, lty=1)
lines(snaivem$mean, col = 4, lty=1)
legend("topleft", lty=1, col=c(1,2,3,4), legend=c("Mean Method", "Naive Method", "Drif Method", "Seasonal Naive"))



#comparaison :
plot(snaivem, plot.conf = F, main="")
Warning in plot.window(xlim, ylim, log, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in title(main = main, xlab = xlab, ylab = ylab, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in axis(1, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in axis(2, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in box(...) : "plot.conf" n'est pas un paramètre graphique
lines(data_ts_test, col = 6, lty=1, lwd=3)


plot(driftm, plot.conf = F, main="")
Warning in plot.window(xlim, ylim, log, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in title(main = main, xlab = xlab, ylab = ylab, ...) :
  "plot.conf" n'est pas un paramètre graphique
Warning in axis(1, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in axis(2, ...) : "plot.conf" n'est pas un paramètre graphique
Warning in box(...) : "plot.conf" n'est pas un paramètre graphique
lines(data_ts_test, col = 6, lty=1, lwd=3)

On regarde : MAE : Mean Absolute Error : RMSE : Root Mean Squarred Error

MASE : Mean Absolute Scaled Error : MAPE : Mean Absolute Percentage Error :

res = pred - val MAE = sum(abs(res))/length(val) RSS = sum(res^2) MSE = RSS/length(val) RMSE = sqrt(MSE)

La plus populaire est la MAPE

MAPE(y_pred, y_true)

$MAPE = (1/n) * Σ(|actual – forecast| / |actu0al|) * 10

“a MAPE value of 6% means that the average difference between the forecasted value and the actual value is 6%”

print(summary(mean))

Forecast method: Mean

Model Information:
$mu
[1] 346667.1

$mu.se
[1] 6731.642

$sd
[1] 65956.35

$bootstrap
[1] FALSE

$call
meanf(y = data_ts_train, h = 8)

attr(,"class")
[1] "meanf"

Error measures:
                       ME     RMSE      MAE       MPE     MAPE    MASE      ACF1
Training set 1.941958e-11 65611.93 55535.08 -3.855657 17.01186 2.16177 0.8254447

Forecasts:
checkresiduals(mean)

    Ljung-Box test

data:  Residuals from Mean
Q* = 731.64, df = 18, p-value < 2.2e-16

Model df: 1.   Total lags used: 19

accuracy(mean, data_ts_test)
                       ME      RMSE       MAE       MPE     MAPE     MASE      ACF1 Theil's U
Training set 1.941958e-11  65611.93  55535.08 -3.855657 17.01186 2.161770 0.8254447        NA
Test set     1.037870e+05 110031.92 103787.04 22.486144 22.48614 4.040036 0.0485288  2.517689
print(summary(naivem))

Forecast method: Naive method

Model Information:
Call: naive(y = data_ts_train, h = 8) 

Residual sd: 36679.9508 

Error measures:
                   ME     RMSE      MAE         MPE     MAPE     MASE       ACF1
Training set 1896.811 36679.95 29013.27 -0.02007386 8.597313 1.129377 -0.2744236

Forecasts:
checkresiduals(naivem)

    Ljung-Box test

data:  Residuals from Naive method
Q* = 248.52, df = 19, p-value < 2.2e-16

Model df: 0.   Total lags used: 19

accuracy(naivem, data_ts_test)
                    ME     RMSE      MAE         MPE     MAPE     MASE       ACF1 Theil's U
Training set  1896.811 36679.95 29013.27 -0.02007386 8.597313 1.129377 -0.2744236        NA
Test set     24357.125 43915.19 38328.62  4.72582164 8.499751 1.491988  0.0485288  1.063155
print(summary(driftm))

Forecast method: Random walk with drift

Model Information:
Call: rwf(y = data_ts_train, h = 8, drift = T) 

Drift: 1896.8105  (se 3778.1861)
Residual sd: 36825.2032 

Error measures:
                       ME     RMSE      MAE        MPE     MAPE    MASE       ACF1
Training set 2.297696e-11 36630.87 28899.04 -0.5861884 8.591266 1.12493 -0.2744236

Forecasts:
checkresiduals(driftm)

    Ljung-Box test

data:  Residuals from Random walk with drift
Q* = 248.52, df = 18, p-value < 2.2e-16

Model df: 1.   Total lags used: 19

accuracy(driftm, data_ts_test)
                       ME     RMSE      MAE        MPE     MAPE     MASE        ACF1 Theil's U
Training set 2.297696e-11 36630.87 28899.04 -0.5861884 8.591266 1.124930 -0.27442358        NA
Test set     1.582148e+04 41314.60 33586.60  2.7843152 7.582963 1.307399  0.06907259  1.007801
print(summary(snaivem))

Forecast method: Seasonal naive method

Model Information:
Call: snaive(y = data_ts_train, h = 8) 

Residual sd: 28666.7301 

Error measures:
                   ME     RMSE      MAE      MPE     MAPE MASE      ACF1
Training set 25337.46 28666.73 25689.63 7.101745 7.207375    1 0.2695124

Forecasts:
checkresiduals(snaivem)

    Ljung-Box test

data:  Residuals from Seasonal naive method
Q* = 35.426, df = 19, p-value = 0.0124

Model df: 0.   Total lags used: 19

accuracy(snaivem, data_ts_test)
                   ME     RMSE      MAE      MPE     MAPE      MASE       ACF1 Theil's U
Training set 25337.46 28666.73 25689.63 7.101745 7.207375 1.0000000  0.2695124        NA
Test set     14263.38 22148.43 16960.88 3.053421 3.648407 0.6602226 -0.5427745 0.4792835

Etude du Modèle de Buys-Ballot

Modèle

https://mpra.ub.uni-muenchen.de/77718/1/MPRA_paper_77718.pdf page 175

L’approche de BUYS-BALLOT consiste à introduire des variables indicatrices correspondant à chaque saison définit par le cycle d’observation. Pour les données trimestrielles, on intègre 4 variables indicatrices. Et pour les données mensuelles, on intègre 12 variables indicatrices.

Le modèle doit alors être estimé (sans constante) avec ces variables indicatrices.

Prédiction des valeurs de 2019

Préparation des données.

Création du modèle

Regression <- lm(trafic~X,data = ts_DataFrame)

\(Xt = Zt + St + \mu t\)

La tendance Prédiction sur les données futurs.

tendance2
       1        2        3        4        5        6        7        8 
450592.7 452735.5 454878.3 457021.1 459163.9 461306.7 463449.5 465592.3 
ts_DataFrame$trafic_residual <- residuals(Regression)

Définissons le mois

ts_DataFrame$mois
 [1] 0.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167 0.0000 0.0833 0.1667 0.2500
[17] 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167 0.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833
[33] 0.6667 0.7500 0.8333 0.9167 0.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167
[49] 0.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167 0.0000 0.0833 0.1667 0.2500
[65] 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167 1.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833
[81] 0.6667 0.7500 0.8333 0.9167 1.0000 0.0833 0.1667 0.2500 0.3333 0.4167 0.5000 0.5833 0.6667 0.7500 0.8333 0.9167

Création du 2nd modèle avec les mois

Regression2 =lm(trafic_residual~0+as.factor(mois),data=ts_DataFrame)

Prédiction de la saisonnalité

prediction2
         1          2          3          4          5          6          7          8          9         10 
 -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 
        11         12         13         14         15         16         17         18         19         20 
-29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404 
        21         22         23         24         25         26         27         28         29         30 
 11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690 
        31         32         33         34         35         36         37         38         39         40 
 -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159 
        41         42         43         44         45         46         47         48         49         50 
 15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871 
        51         52         53         54         55         56         57         58         59         60 
 31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343 
        61         62         63         64         65         66         67         68         69         70 
 -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 
        71         72         73         74         75         76         77         78         79         80 
-29828.920 -18559.343  -4413.396  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404 
        81         82         83         84         85         86         87         88         89         90 
 11589.299  10359.377 -29828.920 -18559.343  -4413.396  -7911.871  31618.207  17647.159  15867.862  39034.690 
        91         92         93         94         95         96 
 -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343 

Prédiction sur les mois

Prediction3
         1          2          3          4          5          6          7          8 
 -4413.396  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404 

Calculons une région de confiance avec l’erreur d’ajustement

ResidusRegression2=residuals(Regression2)
hist(ResidusRegression2)

1.96*sqrt(var(ResidusRegression2))
[1] 19226.16

Auto corrélation de la série temporelle

L’autocorrélation de notre série temporelle correspond à la corrélation entre une mesure du trafic \(t\) et les mesures précédentes \(t - k\) ou les mesures suivantes \(t + k\).

L’auto covariance d’une variable \(Xt\) de moyenne \(\mu\) et d’écart type \(\sigma\) à un décalage \(k\) est donné par la formule

\(\gamma_k= E((X_t-\mu)(X_{t+k}-\mu))\)

On en déduit l’autocorrélation correspondante :

\(\rho_k=\frac{\gamma_k}{\sigma^2}\)

Affichons les autocorrélations de la séries grâce à un corrélogramme

prediction2
         1          2          3          4          5          6          7          8          9         10 
 -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 
        11         12         13         14         15         16         17         18         19         20 
-29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404 
        21         22         23         24         25         26         27         28         29         30 
 11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690 
        31         32         33         34         35         36         37         38         39         40 
 -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871  31618.207  17647.159 
        41         42         43         44         45         46         47         48         49         50 
 15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343  -3764.300  -7911.871 
        51         52         53         54         55         56         57         58         59         60 
 31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343 
        61         62         63         64         65         66         67         68         69         70 
 -3764.300  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404  11589.299  10359.377 
        71         72         73         74         75         76         77         78         79         80 
-29828.920 -18559.343  -4413.396  -7911.871  31618.207  17647.159  15867.862  39034.690  -6546.482 -59343.404 
        81         82         83         84         85         86         87         88         89         90 
 11589.299  10359.377 -29828.920 -18559.343  -4413.396  -7911.871  31618.207  17647.159  15867.862  39034.690 
        91         92         93         94         95         96 
 -6546.482 -59343.404  11589.299  10359.377 -29828.920 -18559.343 

Il est normal que la série soit autocorrélé totalement à elle avec un décalage nulle.

On observe une corrélation forte (0.87) avec un décalage (lag) de 12, cela correspond bien à une saisonnalité annuelle.

print(data.frame(ACF_Sur_Valeurs_Predites$lag,ACF_Sur_Valeurs_Predites$acf)[1:24,])

Recalculons la valeur d’auto-corrélation obtenu en appliquant la formule.

Observons l’application de la formule, en choisissant un décalage de 12

#Constantes
Nombre_Observations=96
decalage=12

#Estimations
moyenneMu=mean(prediction2)
sdSigma=sd(prediction2)


Serie1=prediction2[(decalage+1): 96   ]
Serie2=prediction2[   1 :(96-decalage)]

GammaDecalage12=mean((Serie1-moyenneMu)*(Serie2-moyenneMu))*((Nombre_Observations-decalage)/(Nombre_Observations))

RhoDecalage12=GammaDecalage12/(sdSigma^2)
RhoDecalage12
[1] 0.8658622

Le résultat obtenu est correct. La corrélation avec un décalage de 12 est donc très forte.

la deuxième plus forte corrélation est obsersé avec un décalage de 5, observons cela graphiquement

plot  ( 1:length(prediction2),   prediction2,type="l")
points((1:length(prediction2))-5,prediction2,type="l",col="red")

Cette corrélation est peu pertinente.

print(data.frame(ACF_Sur_Valeurs_Predites$lag,ACF_Sur_Valeurs_Predites$acf)[1:13,])

Après avoir étudier les auto-corrélations sur l’ensemble du modèle, Observons les auto-corrélations sur les résidus du modèle de Buys-Ballot.

  • Texte pour dire que les accidents ne doivent pas être corrélés *
plot(acf(ResidusRegression2))

Pour notre modèle, il n’y a aucune auto-corrélation significative. (symbolisé par la ligne bleu)

Comparaison des prédictions et des valeurs réelles

Affichage de la tendance

Buys_ballot_plot_tendance <- plot(data_ts,
                         main = "Application du modèle de Buys_Ballot",
                         xlab = "Années",
                         ylab = "Nombre de Voyageurs") 

#droite de tendance
lines(Annees,tendance,col="blue",lwd=2)  

#prédiction de la tendance futur
lines(AnneeMoisNumericFutur,tendance2,col="red")

NA
NA

Affichage du modèle de Buys Ballot


Buys_ballot_plot <- plot(data_ts,
                         main = "Application du modèle de Buys_Ballot",
                         xlab = "Années",
                         ylab = "Nombre de Voyageurs") 



#prédiction du modèle de Buys ballot
lines(Annees,tendance+prediction2,col="blue",lwd=2)

#Interval de confiance
 polygon(c(AnneeMoisNumericFutur,rev(AnneeMoisNumericFutur)),
 c(tendance2+Prediction3-1.96*sqrt(var(ResidusRegression2)),
 rev(tendance2+Prediction3+1.96*sqrt(var(ResidusRegression2)))),
 col="cadetblue1",border=NA)
 
 #Prediction des valeurs
 lines(AnneeMoisNumericFutur,tendance2+Prediction3,col="blue",lwd=2)
 
 
 lines(data_ts_test,col="black",lwd=3)

Affichage de la prédiction sur les 8 mois de 2020


Buys_ballot_plot <- plot(data_ts_test,
                         main = "Application du modèle de Buys_Ballot",
                         xlab = "Années",
                         ylab = "Nombre de Voyageurs") 



#prédiction du modèle de Buys ballot
lines(Annees,tendance+prediction2,col="blue",lwd=2)

#Interval de confiance
 polygon(c(AnneeMoisNumericFutur,rev(AnneeMoisNumericFutur)),
 c(tendance2+Prediction3-1.96*sqrt(var(ResidusRegression2)),
 rev(tendance2+Prediction3+1.96*sqrt(var(ResidusRegression2)))),
 col="cadetblue1",border=NA)
 
 #Prediction des valeurs
 lines(AnneeMoisNumericFutur,tendance2+Prediction3,col="blue",lwd=2)
 
 
 lines(data_ts_test,col="black",lwd=3)

Préparation DataFrame pour affichage ggplot

DataAffichageGGplot = as.data.frame(data_ts)
DataAffichageGGplot$Annees = c(Annees, AnneeMoisNumericFutur)
DataAffichageGGplot$AnneesRound = round(DataAffichageGGplot$Annees)
DataAffichageGGplot$PredictionTendance = c(tendance ,tendance2)
DataAffichageGGplot$BuysBalotModele = c(tendance+prediction2,tendance2+Prediction3 )

Reproduisons les graphiques avec ggplot2 pour un résultat plus professsionnel.

library(ggplot2)
library(ggthemes)

p <- ggplot(data =DataAffichageGGplot, aes(x = Annees) ) + 

  geom_line(aes(y = trafic ), size = 0.9, alpha = 0.7)+

  #geom_line(aes(y = PredictionTendance), size = 0.6, alpha = 0.85,linetype="twodash" )+
  
  geom_line(aes(y = BuysBalotModele), size = 1.2, alpha = 0.6, color = "blue")+
  labs(title = "Application du modèle de Buys_Ballot",
       x="Années",
         y= "Nombre de Voyageurs")+
theme_fivethirtyeight()+
  theme(axis.title = element_text(), text = element_text(family = "Rubik")) 

#sur l'année 2019
p2 <- ggplot(data =DataAffichageGGplot, aes(x = Annees) ) + 
  geom_line(aes(y = trafic ), size = 1.2, alpha = 0.7)+
  geom_line(aes(y = BuysBalotModele), size = 1.4, alpha = 0.6, color = "blue")+
theme_fivethirtyeight()+
   xlim (2019.0, 2019.583) +
  ylim (435000, 520000) 


#Ajout zoom sur 2019
p + 
  annotation_custom(ggplotGrob(p2), xmin = 2015, xmax = 2020, ymin = 50000, ymax = 280000) +
  geom_rect(aes(xmin = 2015, xmax = 2020, ymin = 50000, ymax = 280000), color='black', linetype='dashed', alpha=0) 

NA
NA
NA

Nous avons réussi à ajuster une droite de régression. on remarque que la prédiction semble bien correspondre à la réalité si on fait abstraction du dernier mois où le nombre de voyageurs a bien plus chuté que la prédiction du modèle de Buys-Balot.

Comparons avec un ajustement local réalisé par lissage moyennes mobiles.

Comparaison avec les valeurs observées

Lissage moyenne mobile

Définition

Mettre belle formule en latex ici

Choix Moyenne mobiles

Conservation & Annulation

Lissage exponentielle

Lissage simple

fcst_se <- ses(data_ts_train, h = 8)
print(summary(fcst_se))

Forecast method: Simple exponential smoothing

Model Information:
Simple exponential smoothing 

Call:
 ses(y = data_ts_train, h = 8) 

  Smoothing parameters:
    alpha = 0.2559 

  Initial states:
    l = 258126.0245 

  sigma:  31480.96

     AIC     AICc      BIC 
2430.727 2430.988 2438.420 

Error measures:
                   ME     RMSE      MAE      MPE     MAPE     MASE      ACF1
Training set 7057.127 31151.31 25752.89 1.326234 7.684321 1.002462 0.0711143

Forecasts:
checkresiduals(fcst_se)

    Ljung-Box test

data:  Residuals from Simple exponential smoothing
Q* = 144.66, df = 17, p-value < 2.2e-16

Model df: 2.   Total lags used: 19

plot(fcst_se)
lines(data_ts_test, col="red")



df_se = as.data.frame(fcst_se)
predict_value_se <- df_se$`Point Forecast`
MAPE(predict_value_se, data_ts_test)*100
[1] 7.658334

Optimisation du modèle

Fit Exponential Smoothing model -> trouve le meilleur lissage expo

fit_ets <- ets(data_ts_train) 
print(summary(fit_ets))
ETS(A,A,A) 

Call:
 ets(y = data_ts_train) 

  Smoothing parameters:
    alpha = 0.1568 
    beta  = 1e-04 
    gamma = 1e-04 

  Initial states:
    l = 248267.1099 
    b = 2163.3982 
    s = -17928.3 -29535.73 9295.935 11005.81 -57117.85 -7708.17
           38272.64 14592.34 16899.53 34763.15 -7344.204 -5195.15

  sigma:  11014.45

     AIC     AICc      BIC 
2241.611 2249.458 2285.205 

Training set error measures:
                    ME     RMSE      MAE        MPE     MAPE      MASE       ACF1
Training set -458.6799 10054.77 7831.554 -0.2623253 2.371375 0.3048527 0.09626331
checkresiduals(fit_ets)

    Ljung-Box test

data:  Residuals from ETS(A,A,A)
Q* = 7.1794, df = 3, p-value = 0.06639

Model df: 16.   Total lags used: 19

fcst_ets <- forecast(fit_ets, h=8)
plot(fcst_ets)
lines(data_ts_test, col="red")



df_ets = as.data.frame(fcst_ets)
predict_value_ets = df_ets$`Point Forecast`
MAPE(predict_value_ets, data_ts_test)*100
[1] 3.005848

Modèle Arima Automatique

# retourne les meilleurs paramètres 
# d=1 enleve la tendance
# D=1 enleve la saisonnalité 
# => avoir des données stationnaires
# trace : voir les résultats
fit_arima <- auto.arima(data_ts_train, d=1, D=1, stepwise = FALSE, approximation = FALSE, trace=TRUE)

 ARIMA(0,1,0)(0,1,0)[12]                    : 1846.398
 ARIMA(0,1,0)(0,1,1)[12]                    : 1833.134
 ARIMA(0,1,0)(0,1,2)[12]                    : 1835.211
 ARIMA(0,1,0)(1,1,0)[12]                    : 1833.056
 ARIMA(0,1,0)(1,1,1)[12]                    : 1835.09
 ARIMA(0,1,0)(1,1,2)[12]                    : Inf
 ARIMA(0,1,0)(2,1,0)[12]                    : 1835.207
 ARIMA(0,1,0)(2,1,1)[12]                    : 1837.012
 ARIMA(0,1,0)(2,1,2)[12]                    : 1836.461
 ARIMA(0,1,1)(0,1,0)[12]                    : 1814.951
 ARIMA(0,1,1)(0,1,1)[12]                    : 1801.155
 ARIMA(0,1,1)(0,1,2)[12]                    : 1803.362
 ARIMA(0,1,1)(1,1,0)[12]                    : 1803.592
 ARIMA(0,1,1)(1,1,1)[12]                    : 1803.361
 ARIMA(0,1,1)(1,1,2)[12]                    : Inf
 ARIMA(0,1,1)(2,1,0)[12]                    : 1805.004
 ARIMA(0,1,1)(2,1,1)[12]                    : 1805.397
 ARIMA(0,1,1)(2,1,2)[12]                    : Inf
 ARIMA(0,1,2)(0,1,0)[12]                    : 1816.915
 ARIMA(0,1,2)(0,1,1)[12]                    : 1803.033
 ARIMA(0,1,2)(0,1,2)[12]                    : 1805.296
 ARIMA(0,1,2)(1,1,0)[12]                    : 1805.702
 ARIMA(0,1,2)(1,1,1)[12]                    : 1805.295
 ARIMA(0,1,2)(1,1,2)[12]                    : Inf
 ARIMA(0,1,2)(2,1,0)[12]                    : 1807.026
 ARIMA(0,1,2)(2,1,1)[12]                    : 1807.441
 ARIMA(0,1,3)(0,1,0)[12]                    : 1817.787
 ARIMA(0,1,3)(0,1,1)[12]                    : Inf
 ARIMA(0,1,3)(0,1,2)[12]                    : Inf
 ARIMA(0,1,3)(1,1,0)[12]                    : Inf
 ARIMA(0,1,3)(1,1,1)[12]                    : Inf
 ARIMA(0,1,3)(2,1,0)[12]                    : Inf
 ARIMA(0,1,4)(0,1,0)[12]                    : 1820.052
 ARIMA(0,1,4)(0,1,1)[12]                    : Inf
 ARIMA(0,1,4)(1,1,0)[12]                    : Inf
 ARIMA(0,1,5)(0,1,0)[12]                    : Inf
 ARIMA(1,1,0)(0,1,0)[12]                    : 1825.579
 ARIMA(1,1,0)(0,1,1)[12]                    : 1812.512
 ARIMA(1,1,0)(0,1,2)[12]                    : 1814.657
 ARIMA(1,1,0)(1,1,0)[12]                    : 1813.2
 ARIMA(1,1,0)(1,1,1)[12]                    : 1814.614
 ARIMA(1,1,0)(1,1,2)[12]                    : 1816.192
 ARIMA(1,1,0)(2,1,0)[12]                    : 1815.227
 ARIMA(1,1,0)(2,1,1)[12]                    : Inf
 ARIMA(1,1,0)(2,1,2)[12]                    : 1817.796
 ARIMA(1,1,1)(0,1,0)[12]                    : 1816.841
 ARIMA(1,1,1)(0,1,1)[12]                    : 1802.853
 ARIMA(1,1,1)(0,1,2)[12]                    : 1805.117
 ARIMA(1,1,1)(1,1,0)[12]                    : 1805.653
 ARIMA(1,1,1)(1,1,1)[12]                    : Inf
 ARIMA(1,1,1)(1,1,2)[12]                    : Inf
 ARIMA(1,1,1)(2,1,0)[12]                    : Inf
 ARIMA(1,1,1)(2,1,1)[12]                    : Inf
 ARIMA(1,1,2)(0,1,0)[12]                    : 1819.234
 ARIMA(1,1,2)(0,1,1)[12]                    : 1805.22
 ARIMA(1,1,2)(0,1,2)[12]                    : 1807.539
 ARIMA(1,1,2)(1,1,0)[12]                    : 1807.381
 ARIMA(1,1,2)(1,1,1)[12]                    : 1807.538
 ARIMA(1,1,2)(2,1,0)[12]                    : 1808.925
 ARIMA(1,1,3)(0,1,0)[12]                    : 1820.05
 ARIMA(1,1,3)(0,1,1)[12]                    : 1806.055
 ARIMA(1,1,3)(1,1,0)[12]                    : 1808.732
 ARIMA(1,1,4)(0,1,0)[12]                    : Inf
 ARIMA(2,1,0)(0,1,0)[12]                    : 1824.435
 ARIMA(2,1,0)(0,1,1)[12]                    : 1811.07
 ARIMA(2,1,0)(0,1,2)[12]                    : 1813.287
 ARIMA(2,1,0)(1,1,0)[12]                    : 1811.619
 ARIMA(2,1,0)(1,1,1)[12]                    : 1813.247
 ARIMA(2,1,0)(1,1,2)[12]                    : Inf
 ARIMA(2,1,0)(2,1,0)[12]                    : 1813.821
 ARIMA(2,1,0)(2,1,1)[12]                    : 1815.872
 ARIMA(2,1,1)(0,1,0)[12]                    : Inf
 ARIMA(2,1,1)(0,1,1)[12]                    : Inf
 ARIMA(2,1,1)(0,1,2)[12]                    : Inf
 ARIMA(2,1,1)(1,1,0)[12]                    : Inf
 ARIMA(2,1,1)(1,1,1)[12]                    : Inf
 ARIMA(2,1,1)(2,1,0)[12]                    : Inf
 ARIMA(2,1,2)(0,1,0)[12]                    : Inf
 ARIMA(2,1,2)(0,1,1)[12]                    : Inf
 ARIMA(2,1,2)(1,1,0)[12]                    : Inf
 ARIMA(2,1,3)(0,1,0)[12]                    : Inf
 ARIMA(3,1,0)(0,1,0)[12]                    : 1823.646
 ARIMA(3,1,0)(0,1,1)[12]                    : 1808.49
 ARIMA(3,1,0)(0,1,2)[12]                    : 1810.542
 ARIMA(3,1,0)(1,1,0)[12]                    : 1808.594
 ARIMA(3,1,0)(1,1,1)[12]                    : 1810.321
 ARIMA(3,1,0)(2,1,0)[12]                    : 1810.708
 ARIMA(3,1,1)(0,1,0)[12]                    : Inf
 ARIMA(3,1,1)(0,1,1)[12]                    : Inf
 ARIMA(3,1,1)(1,1,0)[12]                    : Inf
 ARIMA(3,1,2)(0,1,0)[12]                    : Inf
 ARIMA(4,1,0)(0,1,0)[12]                    : 1823.996
 ARIMA(4,1,0)(0,1,1)[12]                    : 1810.199
 ARIMA(4,1,0)(1,1,0)[12]                    : 1810.845
 ARIMA(4,1,1)(0,1,0)[12]                    : Inf
 ARIMA(5,1,0)(0,1,0)[12]                    : 1825.055



 Best model: ARIMA(0,1,1)(0,1,1)[12]                    
print(summary(fit_arima))
Series: data_ts_train 
ARIMA(0,1,1)(0,1,1)[12] 

Coefficients:
          ma1     sma1
      -0.7675  -0.5465
s.e.   0.0977   0.1295

sigma^2 = 138827719:  log likelihood = -897.43
AIC=1800.85   AICc=1801.16   BIC=1808.11

Training set error measures:
                   ME     RMSE      MAE       MPE     MAPE      MASE       ACF1
Training set 805.2378 10822.93 7747.841 0.2158443 2.213481 0.3015941 0.03453594
checkresiduals(fit_arima)

    Ljung-Box test

data:  Residuals from ARIMA(0,1,1)(0,1,1)[12]
Q* = 10.898, df = 17, p-value = 0.8618

Model df: 2.   Total lags used: 19

fcst_arima <- forecast(fit_arima, h=8)
plot(fcst_arima)
lines(data_ts_test, col='red')



df_arima = as.data.frame(fcst_arima)
predict_value_arima = df_arima$`Point Forecast`
MAPE(predict_value_arima, data_ts_test)*100
[1] 2.814135
LS0tDQp0aXRsZTogfA0KICANCmF1dGhvcjogDQotIENsb3ZpcyBEZWxldHJlDQotIENoYXJsZXMgVml0cnkNCmRhdGU6DQpvdXRwdXQ6DQogIGh0bWxfbm90ZWJvb2s6DQogICAgdGhlbWU6IGNlcnVsZWFuDQogICAgbnVtYmVyX3NlY3Rpb25zOiBubw0KICAgIHRvYzogeWVzDQogICAgdG9jX2Zsb2F0OiB0cnVlDQplZGl0b3Jfb3B0aW9uczogDQogIG1hcmtkb3duOiANCiAgICB3cmFwOiA3Mg0KLS0tDQoNCmBgYHs9aHRtbH0NCjxzdHlsZSB0eXBlPSJ0ZXh0L2NzcyI+DQoNCmJvZHl7IC8qIE5vcm1hbCAgKi8NCiAgICAgIGZvbnQtc2l6ZTogMjBweDsNCiAgfQ0KdGQgeyAgLyogVGFibGUgICovDQogIGZvbnQtc2l6ZTogOHB4Ow0KfQ0KaDEudGl0bGUgew0KICBmb250LXNpemU6IDU1cHg7DQogIGNvbG9yOiBEYXJrQmx1ZTsNCn0NCmgxIHsgLyogSGVhZGVyIDEgKi8NCiAgZm9udC1zaXplOiAzOHB4Ow0KICBjb2xvcjogRGFya0JsdWU7DQp9DQpoMiB7IC8qIEhlYWRlciAyICovDQogICAgZm9udC1zaXplOiAyOHB4Ow0KICBjb2xvcjogRGFya0JsdWU7DQp9DQpoMyB7IC8qIEhlYWRlciAzICovDQogIGZvbnQtc2l6ZTogMzVweDsNCiAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogIGNvbG9yOiBEYXJrQmx1ZTsNCn0NCmNvZGUucnsgLyogQ29kZSBibG9jayAqLw0KICAgIGZvbnQtc2l6ZTogMTJweDsNCn0NCnByZSB7IC8qIENvZGUgYmxvY2sgLSBkZXRlcm1pbmVzIGNvZGUgc3BhY2luZyBiZXR3ZWVuIGxpbmVzICovDQogICAgZm9udC1zaXplOiAxNHB4Ow0KfQ0KPC9zdHlsZT4NCmBgYA0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUpDQoNCnNvdXJjZSgiRm9uY3Rpb25zLlIiLCBsb2NhbCA9IGtuaXRyOjprbml0X2dsb2JhbCgpKQ0KDQojaW5zdGFsbCBmb3IgZXhwb3J0IGluIHBkZiBmaWxlDQojdGlueXRleDo6aW5zdGFsbF90aW55dGV4KCkNCmBgYA0KDQo8YnI+IDwvYnI+DQoNCmBgYHtyIGluY2x1ZGU9RkFMU0V9DQppZighcmVxdWlyZShmb3JlY2FzdCkpIGluc3RhbGwucGFja2FnZXMoInRtIiwgcmVwb3MgPSAiaHR0cDovL2NyYW4udXMuci1wcm9qZWN0Lm9yZyIpDQpyZXF1aXJlKGZvcmVjYXN0KQ0KDQppZighcmVxdWlyZShmcHAyKSkgaW5zdGFsbC5wYWNrYWdlcygidG0iLCByZXBvcyA9ICJodHRwOi8vY3Jhbi51cy5yLXByb2plY3Qub3JnIikNCnJlcXVpcmUoZnBwMikNCg0KaWYoIXJlcXVpcmUoTUxtZXRyaWNzKSkgaW5zdGFsbC5wYWNrYWdlcygidG0iLCByZXBvcyA9ICJodHRwOi8vY3Jhbi51cy5yLXByb2plY3Qub3JnIikNCnJlcXVpcmUoTUxtZXRyaWNzKQ0KDQppZighcmVxdWlyZShnZ3Bsb3QyKSkgaW5zdGFsbC5wYWNrYWdlcygidG0iLCByZXBvcyA9ICJodHRwOi8vY3Jhbi51cy5yLXByb2plY3Qub3JnIikNCnJlcXVpcmUoZ2dwbG90MikNCg0KaWYoIXJlcXVpcmUoZnBwMikpIGluc3RhbGwucGFja2FnZXMoInRtIiwgcmVwb3MgPSAiaHR0cDovL2NyYW4udXMuci1wcm9qZWN0Lm9yZyIpDQpyZXF1aXJlKGZwcDIpDQoNCmlmKCFyZXF1aXJlKFRTc3R1ZGlvKSkgaW5zdGFsbC5wYWNrYWdlcygidG0iLCByZXBvcyA9ICJodHRwOi8vY3Jhbi51cy5yLXByb2plY3Qub3JnIikNCnJlcXVpcmUoVFNzdHVkaW8pDQpgYGANCg0KIyBJbnRyb2R1Y3Rpb24NCg0KTm91cyBzb3VoYWl0b25zIHLDqWFsaXPDqSBsJyoqw6l0dWRlIGQndW5lIHPDqXJpZSB0ZW1wb3JlbGxlKiogZXQgZmFpcmUgZGVzDQpwcsOpdmlzaW9ucyBzdXIgY2VsbGUtY2kuDQoNCkNldHRlIHPDqXJpZSB0ZW1wb3JlbGxlIGVzdCBsZSB0cmFmaWMgbWVuc3VlbCBkJ3VuZSBDb21wYWduaWUgYcOpcmllbm5lIGRlDQpqYW52aWVyIDIwMTEgw6AgYW/Du3QgMjAxOS4NCg0KTm9zIHByw6l2aXNpb25zIHBvcnRlbnQgc3VyIGxlcyA4IG1vaXMgZGUgbCdhbm7DqWUgMjAxOQ0KDQojIFJlcHLDqXNlbnRhdGlvbiBncmFwaGlxdWUgZGUgbGEgc8OpcmllLg0KDQojIyBJbXBvcnQgZGVzIGRvbm7DqWVzDQoNCkltcG9ydCBkZSBsYSBiYXNlLCBvbiBzw6lsZWN0aW9ubmUgbGEgY29sb25uZSBkZXMgdmFsZXVycw0KDQpgYGB7cn0NCmxpYnJhcnkocmVhZHIpDQpkYXRhIDwtIHJlYWRfZGVsaW0oIlRyYWZpYy12b3lhZ2V1cnMuY3N2IiwgDQogICAgZGVsaW0gPSAiOyIsIGxvY2FsZSA9IGxvY2FsZShlbmNvZGluZyA9ICJJU08tODg1OS0xIikpDQpgYGANCg0KYGBge3J9DQpzdW1tYXJ5KGRhdGEpDQpgYGANCg0KYGBge3J9DQpkYXRhX3ZhbHVlIDwtIGRhdGFbLDJdDQpgYGANCg0KIyMgQWZmaWNoYWdlDQoNCkNyw6lhdGlvbiBkZSBsYSBzw6lyaWUgY2hyb25vbG9naXF1ZSA6DQoNCmBgYHtyfQ0KbGlicmFyeShUU3N0dWRpbykNCmRhdGFfdHMgPC0gdHMoZGF0YV92YWx1ZSwgc3RhcnQ9MjAxMSwgZnJlcXVlbmN5PTEyKQ0KcGxvdF8xX1RpbWVTZXJpZXMoZGF0YV90cykNCmBgYA0KDQojIyBTw6lwYXJhdGlvbiBqZXUgZGUgZG9ubsOpZXMNCg0KYGBge3J9DQojcmV2b2lyIGwgYWZmaWNoYWdlIGNhciBjYSBwcmVuZCBwYXMgZW4gY29tcHRlIHR0IDIwMTkNCmRhdGFfdHNfdHJhaW4gPC0gd2luZG93KGRhdGFfdHMsIHN0YXJ0ID0gYygyMDExLCAxKSwgZW5kID0gYygyMDE4LDEyKSkNCmRhdGFfdHNfdGVzdCA8LSB3aW5kb3coZGF0YV90cywgc3RhcnQ9IGMoMjAxOSwxKSwgZW5kID0gYygyMDE5LDgpKQ0KDQpwbG90KGRhdGFfdHMsIHhsaW09YygyMDExLDIwMjApKQ0KbGluZXMoZGF0YV90c190ZXN0LCBjb2w9MykNCmxlZ2VuZCgidG9wbGVmdCIsIGx0eSA9IDEsIGNvbD1jKDEsMyksIGxlZ2VuZD1jKCJTw6lyaWUgY2hyb25vbG9naXF1ZSBUcmFpbiIsICJTw6lyaWUgY2hyb25vbG9naXF1ZSBUZXN0IikpDQpgYGANCg0KLT4gc3Ryb25nIHRyZW5kIC0+IHBhdGVybiBxdWkgc2UgcmVwZXRlLCBzYWlzb25uYWxpdMOpID8NCg0KIyMgUmVwcsOpc2VudGF0aW9uIGRlIGxhIHNhaXNvbm5hbGl0w6kNCg0KQW5hbHlzZSBkZSBsYSBzYWlzb25uYWxpdMOpIGVuIHN1cGVycG9zYW50IGNoYXF1ZSBhbm7DqWUgKHBhciBtb2lzKToNCg0KLT4gZW4gc3VwcHJpbWFudCBsYSB0ZW5kYW5jZSBvbiB2b2l0IGJpZW4gbGEgc2Fpc29ubmFsaXTDqSA9Pg0Kc2Fpc29ubmFsaXTDqSByw6lndWxpw6hyZQ0KDQpgYGB7cn0NCmdnc2Vhc29ucGxvdChkYXRhX3RzKQ0KZGF0YV90c193aXRob3V0X3RyZW5kID0gZGlmZihkYXRhX3RzKQ0KZ2dzZWFzb25wbG90KGRhdGFfdHNfd2l0aG91dF90cmVuZCkNCmBgYA0KDQojIyBSZXByw6lzZW50YXRpb24gZGVzIGTDqWNvbXBvc2l0aW9ucyBwb3NzaWJsZXMNCg0KREVDT01QT1NJVElPTiA6IGFkZGl0aXZlIC8gTXVsdGlwbGljYXRpdmUgVHMgPSBUcmVuZCArIFNlYXNvbmFsICsgUmFuZG9tDQovIFRzID0gVHJlbmQgXCogU2Vhc29uYWwgXCogUmFuZG9tDQoNCmBgYHtyfQ0KZGVjb21wb3NlZF9kYXRhIDwtIGRlY29tcG9zZShkYXRhX3RzX3RyYWluLCB0eXBlPSJhZGRpdGl2ZSIpDQpwbG90KGRlY29tcG9zZWRfZGF0YSR0cmVuZCkNCnBsb3QoZGVjb21wb3NlZF9kYXRhJHNlYXNvbmFsKQ0KcGxvdChkZWNvbXBvc2VkX2RhdGEkcmFuZG9tKQ0KDQpib3hwbG90KGRhdGFfdHMgfiBjeWNsZShkYXRhX3RzKSkNCmBgYA0KDQotPiBvbiBkaXN0aW5ndWUgZGVzIHNhaXNvbm5hbGl0w6lzID0+IGZhaXJlIHLDqWdyZXNzaW9uIGNhIG4nYSBwYXMgZGUgc2Vucw0KPT4gbW9kw6hsZSBkZSBCdXlzIEJhbGxvdA0KDQotPiBib25uZSByZXBhcnRpdGlvbiBkdSBicnVpdCAtPiBxdWVscXVlcyBvdXRsaWVycw0KDQpgYGB7cn0NCmNoZWNrcmVzaWR1YWxzKHJlbWFpbmRlcihkZWNvbXBvc2VkX2RhdGEpKQ0KYGBgDQoNCk9uIGEgdGVuZGFuY2VzICsgc2Fpc29ubmFsaXTDqQ0KDQoNCiMgTW9kw6hsZXMgZXNwYWNlLcOpdGF0DQoNCi0gICBtZWFuZiA6IEF2ZXJhZ2UgTWV0aG9kIDogcHJlbmQgbGEgdmFsZXVyIG1veWVubmUgZGUgdG91dGUgbGVzDQogICAgb2JzZXJ2YXRpb25zIHBvdXIgdG91dGVzIGxlcyBwcsOpZGljdGlvbnMsDQotICAgbmFpdmUgOiBOYWl2ZSBNZXRob2QgOiBwcmVuZCBsYSBkZXJuacOocmUgb2JzZXJ2YXRpb24gcG91ciB0b3V0ZXMgbGVzDQogICAgcHLDqWRpY3Rpb25zLA0KLSAgIGRyaWZ0IDogRHJpZnQgTWV0aG9kIDogcHJlbmQgbGEgcHJlbWnDqHJlIGV0IGxhIGRlcm5pw6hyZSBvYnNlcnZhdGlvbnMNCiAgICBldCB0cmFjZSB1bmUgbGlnbmVzIGVudHJlIGxlcyBkZXV4LCBvbiB1dGlsaXNlIGxhIGNvdXJiZSBwb3VyIGxlcw0KICAgIHByw6lkaWN0aW9ucywNCi0gICBzbmFpdmUgOiBTZWFzb25hbCBOYWl2ZSBGb3JlY2FzdCA6IFByZW5kIGxhIGRlcm5pw6hyZSB2YWxldXIgZGUgbGENCiAgICBzYWlzb24gcHLDqWPDqWRlbnRlIGNvbW1lIHByw6lkaWN0aW9uIChleCA6IHNlcHQgMjAxOCA9IHNlcCAyMDE5ICsNCiAgICBlcnJldXIpDQoNCmBgYHtyfQ0KbGlicmFyeShmb3JlY2FzdCkNCm1lYW4gPC0gbWVhbmYoZGF0YV90c190cmFpbiwgaD04KQ0KbmFpdmVtIDwtIG5haXZlKGRhdGFfdHNfdHJhaW4sIGg9OCkNCmRyaWZ0bSA8LSByd2YoZGF0YV90c190cmFpbiwgaD04LCBkcmlmPVQpDQpzbmFpdmVtIDwtIHNuYWl2ZShkYXRhX3RzX3RyYWluLCBoPTgpDQpgYGANCg0KYGBge3J9DQpwbG90KG1lYW4sIHBsb3QuY29uZiA9IEYsIG1haW49IiIpDQpsaW5lcyhuYWl2ZW0kbWVhbiwgY29sPTIsIGx0eT0xKQ0KbGluZXMoZHJpZnRtJG1lYW4sIGNvbD01LCBsdHk9MSkNCmxpbmVzKHNuYWl2ZW0kbWVhbiwgY29sID0gNCwgbHR5PTEpDQpsZWdlbmQoInRvcGxlZnQiLCBsdHk9MSwgY29sPWMoMSwyLDMsNCksIGxlZ2VuZD1jKCJNZWFuIE1ldGhvZCIsICJOYWl2ZSBNZXRob2QiLCAiRHJpZiBNZXRob2QiLCAiU2Vhc29uYWwgTmFpdmUiKSkNCg0KDQojY29tcGFyYWlzb24gOg0KcGxvdChzbmFpdmVtLCBwbG90LmNvbmYgPSBGLCBtYWluPSIiKQ0KbGluZXMoZGF0YV90c190ZXN0LCBjb2wgPSA2LCBsdHk9MSwgbHdkPTMpDQoNCnBsb3QoZHJpZnRtLCBwbG90LmNvbmYgPSBGLCBtYWluPSIiKQ0KbGluZXMoZGF0YV90c190ZXN0LCBjb2wgPSA2LCBsdHk9MSwgbHdkPTMpDQoNCmBgYA0KDQpPbiByZWdhcmRlIDogTUFFIDogTWVhbiBBYnNvbHV0ZSBFcnJvciA6IFJNU0UgOiBSb290IE1lYW4gU3F1YXJyZWQgRXJyb3INCg0KOiAgIE1BU0UgOiBNZWFuIEFic29sdXRlIFNjYWxlZCBFcnJvciA6IE1BUEUgOiBNZWFuIEFic29sdXRlIFBlcmNlbnRhZ2UNCiAgICBFcnJvciA6DQoNCnJlcyA9IHByZWQgLSB2YWwgTUFFID0gc3VtKGFicyhyZXMpKS9sZW5ndGgodmFsKSBSU1MgPSBzdW0ocmVzXF4yKSBNU0UgPQ0KUlNTL2xlbmd0aCh2YWwpIFJNU0UgPSBzcXJ0KE1TRSkNCg0KTGEgcGx1cyBwb3B1bGFpcmUgZXN0IGxhIE1BUEUNCg0KTUFQRSh5X3ByZWQsIHlfdHJ1ZSkNCg0KJE1BUEUgPSAoMS9uKSBcKiDOoyhcfGFjdHVhbCAtLSBmb3JlY2FzdFx8IC8gXHxhY3R1MGFsXHwpIFwqIDEwIA0KDQoiYSBNQVBFIHZhbHVlIG9mIDYlIG1lYW5zIHRoYXQgdGhlIGF2ZXJhZ2UgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBmb3JlY2FzdGVkDQp2YWx1ZSBhbmQgdGhlIGFjdHVhbCB2YWx1ZSBpcyA2JSINCg0KYGBge3J9DQpwcmludChzdW1tYXJ5KG1lYW4pKQ0KY2hlY2tyZXNpZHVhbHMobWVhbikNCmFjY3VyYWN5KG1lYW4sIGRhdGFfdHNfdGVzdCkNCg0KYGBgDQoNCmBgYHtyfQ0KcHJpbnQoc3VtbWFyeShuYWl2ZW0pKQ0KY2hlY2tyZXNpZHVhbHMobmFpdmVtKQ0KYWNjdXJhY3kobmFpdmVtLCBkYXRhX3RzX3Rlc3QpDQoNCmBgYA0KDQpgYGB7cn0NCnByaW50KHN1bW1hcnkoZHJpZnRtKSkNCmNoZWNrcmVzaWR1YWxzKGRyaWZ0bSkNCmFjY3VyYWN5KGRyaWZ0bSwgZGF0YV90c190ZXN0KQ0KDQpgYGANCg0KYGBge3J9DQpwcmludChzdW1tYXJ5KHNuYWl2ZW0pKQ0KY2hlY2tyZXNpZHVhbHMoc25haXZlbSkNCmFjY3VyYWN5KHNuYWl2ZW0sIGRhdGFfdHNfdGVzdCkNCg0KYGBgDQoNCg0KDQoNCg0KIyBFdHVkZSBkdSBNb2TDqGxlIGRlIEJ1eXMtQmFsbG90DQoNCiMjIE1vZMOobGUNCg0KPGh0dHBzOi8vbXByYS51Yi51bmktbXVlbmNoZW4uZGUvNzc3MTgvMS9NUFJBX3BhcGVyXzc3NzE4LnBkZj4gcGFnZSAxNzUNCg0KTCdhcHByb2NoZSBkZSBCVVlTLUJBTExPVCBjb25zaXN0ZSDDoCBpbnRyb2R1aXJlIGRlcyB2YXJpYWJsZXMNCmluZGljYXRyaWNlcyBjb3JyZXNwb25kYW50IMOgIGNoYXF1ZSBzYWlzb24gZMOpZmluaXQgcGFyIGxlIGN5Y2xlDQpkJ29ic2VydmF0aW9uLiBQb3VyIGxlcyBkb25uw6llcyB0cmltZXN0cmllbGxlcywgb24gaW50w6hncmUgNCB2YXJpYWJsZXMNCmluZGljYXRyaWNlcy4gRXQgcG91ciBsZXMgZG9ubsOpZXMgbWVuc3VlbGxlcywgb24gaW50w6hncmUgMTIgdmFyaWFibGVzDQppbmRpY2F0cmljZXMuDQoNCkxlIG1vZMOobGUgZG9pdCBhbG9ycyDDqnRyZSBlc3RpbcOpIChzYW5zIGNvbnN0YW50ZSkgYXZlYyBjZXMgdmFyaWFibGVzDQppbmRpY2F0cmljZXMuDQoNCiMjIFByw6lkaWN0aW9uIGRlcyB2YWxldXJzIGRlIDIwMTkNCg0KUHLDqXBhcmF0aW9uIGRlcyBkb25uw6llcy4NCg0KYGBge3J9DQpBbm5lZXM9YXMubnVtZXJpYyh0aW1lKGRhdGFfdHNfdHJhaW4pKQ0KdHNfRGF0YUZyYW1lID1kYXRhLmZyYW1lKHRyYWZpYz1kYXRhX3RzX3RyYWluLFg9YXMubnVtZXJpYyhBbm5lZXMpKQ0KYGBgDQoNCkNyw6lhdGlvbiBkdSBtb2TDqGxlDQoNCmBgYHtyfQ0KUmVncmVzc2lvbiA8LSBsbSh0cmFmaWN+WCxkYXRhID0gdHNfRGF0YUZyYW1lKQ0KYGBgDQoNCiRYdCA9IFp0ICsgU3QgKyBcbXUgdCQNCg0KTGEgdGVuZGFuY2UgUHLDqWRpY3Rpb24gc3VyIGxlcyBkb25uw6llcyBmdXR1cnMuDQoNCmBgYHtyfQ0KdGVuZGFuY2U9cHJlZGljdChSZWdyZXNzaW9uKQ0KDQpBbm5lZU1vaXNOdW1lcmljRnV0dXI9c2VxKG1heChBbm5lZXMpKzEvMTIsbGVuZ3RoPTgsYnk9MS8xMikgICNsZXMgMTAgcHJvY2hhaW5zIG1vaXMNCg0KdGVuZGFuY2UyPXByZWRpY3QoUmVncmVzc2lvbiwgbmV3ZGF0YT1kYXRhLmZyYW1lKFg9QW5uZWVNb2lzTnVtZXJpY0Z1dHVyKSkgDQpgYGANCg0KYGBge3J9DQp0c19EYXRhRnJhbWUkdHJhZmljX3Jlc2lkdWFsIDwtIHJlc2lkdWFscyhSZWdyZXNzaW9uKQ0KYGBgDQoNCkTDqWZpbmlzc29ucyBsZSBtb2lzDQoNCmBgYHtyfQ0KdHNfRGF0YUZyYW1lJG1vaXMgPC0gcm91bmQodHNfRGF0YUZyYW1lJFggLSB0cnVuYyh0c19EYXRhRnJhbWUkWCksZGlnaXQ9NCkNCmBgYA0KDQpDcsOpYXRpb24gZHUgMm5kIG1vZMOobGUgYXZlYyBsZXMgbW9pcw0KDQpgYGB7cn0NClJlZ3Jlc3Npb24yID1sbSh0cmFmaWNfcmVzaWR1YWx+MCthcy5mYWN0b3IobW9pcyksZGF0YT10c19EYXRhRnJhbWUpDQpgYGANCg0KUHLDqWRpY3Rpb24gZGUgbGEgc2Fpc29ubmFsaXTDqQ0KDQpgYGB7cn0NCnByZWRpY3Rpb24yID1wcmVkaWN0KFJlZ3Jlc3Npb24yKQ0KYGBgDQoNClByw6lkaWN0aW9uIHN1ciBsZXMgbW9pcw0KDQpgYGB7cn0NCk1vaXNOdW1lcmljPSByb3VuZChBbm5lZU1vaXNOdW1lcmljRnV0dXIgLSB0cnVuYyhBbm5lZU1vaXNOdW1lcmljRnV0dXINCiAgICAgICAgICAgICAgICAgICAgICksNCkNClByZWRpY3Rpb24zID1wcmVkaWN0KCBSZWdyZXNzaW9uMiwgbmV3ZGF0YT0gZGF0YS5mcmFtZShtb2lzPU1vaXNOdW1lcmljKSkNCg0KYGBgDQoNCkNhbGN1bG9ucyB1bmUgcsOpZ2lvbiBkZSBjb25maWFuY2UgYXZlYyBsJ2VycmV1ciBkJ2FqdXN0ZW1lbnQNCg0KYGBge3J9DQpSZXNpZHVzUmVncmVzc2lvbjI9cmVzaWR1YWxzKFJlZ3Jlc3Npb24yKQ0KaGlzdChSZXNpZHVzUmVncmVzc2lvbjIpDQoxLjk2KnNxcnQodmFyKFJlc2lkdXNSZWdyZXNzaW9uMikpDQpgYGANCg0KIyMgQXV0byBjb3Jyw6lsYXRpb24gZGUgbGEgc8OpcmllIHRlbXBvcmVsbGUNCg0KTCdhdXRvY29ycsOpbGF0aW9uIGRlIG5vdHJlIHPDqXJpZSB0ZW1wb3JlbGxlIGNvcnJlc3BvbmQgw6AgbGEgY29ycsOpbGF0aW9uDQplbnRyZSB1bmUgbWVzdXJlIGR1IHRyYWZpYyAkdCQgZXQgbGVzIG1lc3VyZXMgcHLDqWPDqWRlbnRlcyAkdCAtIGskIG91IGxlcw0KbWVzdXJlcyBzdWl2YW50ZXMgJHQgKyBrJC4NCg0KTCdhdXRvIGNvdmFyaWFuY2UgZCd1bmUgdmFyaWFibGUgJFh0JCBkZSBtb3llbm5lICRcbXUkIGV0IGQnw6ljYXJ0IHR5cGUNCiRcc2lnbWEkIMOgIHVuIGTDqWNhbGFnZSAkayQgZXN0IGRvbm7DqSBwYXIgbGEgZm9ybXVsZQ0KDQokXGdhbW1hX2s9IEUoKFhfdC1cbXUpKFhfe3Qra30tXG11KSkkDQoNCk9uIGVuIGTDqWR1aXQgbCdhdXRvY29ycsOpbGF0aW9uIGNvcnJlc3BvbmRhbnRlIDoNCg0KJFxyaG9faz1cZnJhY3tcZ2FtbWFfa317XHNpZ21hXjJ9JA0KDQpBZmZpY2hvbnMgbGVzIGF1dG9jb3Jyw6lsYXRpb25zIGRlIGxhIHPDqXJpZXMgZ3LDomNlIMOgIHVuIGNvcnLDqWxvZ3JhbW1lDQoNCmBgYHtyfQ0KQUNGX1N1cl9WYWxldXJzX1ByZWRpdGVzIDwtIGFjZihwcmVkaWN0aW9uMikNCmBgYA0KDQpJbCBlc3Qgbm9ybWFsIHF1ZSBsYSBzw6lyaWUgc29pdCBhdXRvY29ycsOpbMOpIHRvdGFsZW1lbnQgw6AgZWxsZSBhdmVjIHVuDQpkw6ljYWxhZ2UgbnVsbGUuDQoNCk9uIG9ic2VydmUgdW5lIGNvcnLDqWxhdGlvbiBmb3J0ZSAoMC44NykgYXZlYyB1biBkw6ljYWxhZ2UgKGxhZykgZGUgMTIsDQpjZWxhIGNvcnJlc3BvbmQgYmllbiDDoCB1bmUgc2Fpc29ubmFsaXTDqSBhbm51ZWxsZS4NCg0KYGBge3J9DQpwcmludChkYXRhLmZyYW1lKEFDRl9TdXJfVmFsZXVyc19QcmVkaXRlcyRsYWcsQUNGX1N1cl9WYWxldXJzX1ByZWRpdGVzJGFjZilbMToxMyxdKQ0KYGBgDQoNClJlY2FsY3Vsb25zIGxhIHZhbGV1ciBkJ2F1dG8tY29ycsOpbGF0aW9uIG9idGVudSBlbiBhcHBsaXF1YW50IGxhIGZvcm11bGUuDQoNCk9ic2Vydm9ucyBsJ2FwcGxpY2F0aW9uIGRlIGxhIGZvcm11bGUsIGVuIGNob2lzaXNzYW50IHVuDQpkw6ljYWxhZ2UgZGUgMTINCg0KYGBge3J9DQojQ29uc3RhbnRlcw0KTm9tYnJlX09ic2VydmF0aW9ucz05Ng0KZGVjYWxhZ2U9MTINCg0KI0VzdGltYXRpb25zDQptb3llbm5lTXU9bWVhbihwcmVkaWN0aW9uMikNCnNkU2lnbWE9c2QocHJlZGljdGlvbjIpDQoNCg0KU2VyaWUxPXByZWRpY3Rpb24yWyhkZWNhbGFnZSsxKTogOTYgICBdDQpTZXJpZTI9cHJlZGljdGlvbjJbICAgMSA6KDk2LWRlY2FsYWdlKV0NCg0KR2FtbWFEZWNhbGFnZTEyPW1lYW4oKFNlcmllMS1tb3llbm5lTXUpKihTZXJpZTItbW95ZW5uZU11KSkqKChOb21icmVfT2JzZXJ2YXRpb25zLWRlY2FsYWdlKS8oTm9tYnJlX09ic2VydmF0aW9ucykpDQoNClJob0RlY2FsYWdlMTI9R2FtbWFEZWNhbGFnZTEyLyhzZFNpZ21hXjIpDQpSaG9EZWNhbGFnZTEyDQpgYGANCg0KTGUgcsOpc3VsdGF0IG9idGVudSBlc3QgY29ycmVjdC4gTGEgY29ycsOpbGF0aW9uIGF2ZWMgdW4gZMOpY2FsYWdlIGRlIDEyIGVzdCBkb25jIHRyw6hzIGZvcnRlLg0KDQoNCg0KbGEgZGV1eGnDqG1lIHBsdXMgZm9ydGUgY29ycsOpbGF0aW9uIGVzdCBvYnNlcnPDqSBhdmVjIHVuIGTDqWNhbGFnZSBkZSA1LA0Kb2JzZXJ2b25zIGNlbGEgZ3JhcGhpcXVlbWVudA0KDQpgYGB7cn0NCnBsb3QgICggMTpsZW5ndGgocHJlZGljdGlvbjIpLCAgIHByZWRpY3Rpb24yLHR5cGU9ImwiKQ0KcG9pbnRzKCgxOmxlbmd0aChwcmVkaWN0aW9uMikpLTUscHJlZGljdGlvbjIsdHlwZT0ibCIsY29sPSJyZWQiKQ0KYGBgDQoNCkNldHRlIGNvcnLDqWxhdGlvbiBlc3QgcGV1IHBlcnRpbmVudGUuDQoNCg0KDQpgYGB7cn0NCnByaW50KGRhdGEuZnJhbWUoQUNGX1N1cl9WYWxldXJzX1ByZWRpdGVzJGxhZyxBQ0ZfU3VyX1ZhbGV1cnNfUHJlZGl0ZXMkYWNmKVsxOjEzLF0pDQpgYGANCg0KQXByw6hzIGF2b2lyIMOpdHVkaWVyIGxlcyBhdXRvLWNvcnLDqWxhdGlvbnMgc3VyIGwnZW5zZW1ibGUgZHUgbW9kw6hsZSwNCk9ic2Vydm9ucyBsZXMgYXV0by1jb3Jyw6lsYXRpb25zIHN1ciBsZXMgcsOpc2lkdXMgZHUgbW9kw6hsZSBkZSBCdXlzLUJhbGxvdC4NCg0KKiBUZXh0ZSBwb3VyIGRpcmUgcXVlIGxlcyBhY2NpZGVudHMgbmUgZG9pdmVudCBwYXMgw6p0cmUgY29ycsOpbMOpcyAqDQoNCg0KYGBge3J9DQpwbG90KGFjZihSZXNpZHVzUmVncmVzc2lvbjIpKQ0KYGBgDQpQb3VyIG5vdHJlIG1vZMOobGUsIGlsIG4neSBhIGF1Y3VuZSBhdXRvLWNvcnLDqWxhdGlvbiBzaWduaWZpY2F0aXZlLiAoc3ltYm9saXPDqSBwYXIgbGEgbGlnbmUgYmxldSkNCg0KDQoNCiMjIENvbXBhcmFpc29uIGRlcyBwcsOpZGljdGlvbnMgZXQgZGVzIHZhbGV1cnMgcsOpZWxsZXMNCg0KQWZmaWNoYWdlIGRlIGxhIHRlbmRhbmNlDQoNCmBgYHtyIHdhcm5pbmc9RkFMU0V9DQpCdXlzX2JhbGxvdF9wbG90X3RlbmRhbmNlIDwtIHBsb3QoZGF0YV90cywNCiAgICAgICAgICAgICAgICAgICAgICAgICBtYWluID0gIkFwcGxpY2F0aW9uIGR1IG1vZMOobGUgZGUgQnV5c19CYWxsb3QiLA0KICAgICAgICAgICAgICAgICAgICAgICAgIHhsYWIgPSAiQW5uw6llcyIsDQogICAgICAgICAgICAgICAgICAgICAgICAgeWxhYiA9ICJOb21icmUgZGUgVm95YWdldXJzIikgDQoNCiNkcm9pdGUgZGUgdGVuZGFuY2UNCmxpbmVzKEFubmVlcyx0ZW5kYW5jZSxjb2w9ImJsdWUiLGx3ZD0yKSAgDQoNCiNwcsOpZGljdGlvbiBkZSBsYSB0ZW5kYW5jZSBmdXR1cg0KbGluZXMoQW5uZWVNb2lzTnVtZXJpY0Z1dHVyLHRlbmRhbmNlMixjb2w9InJlZCIpDQoNCg0KYGBgDQoNCkFmZmljaGFnZSBkdSBtb2TDqGxlIGRlIEJ1eXMgQmFsbG90DQoNCmBgYHtyfQ0KDQpCdXlzX2JhbGxvdF9wbG90IDwtIHBsb3QoZGF0YV90cywNCiAgICAgICAgICAgICAgICAgICAgICAgICBtYWluID0gIkFwcGxpY2F0aW9uIGR1IG1vZMOobGUgZGUgQnV5c19CYWxsb3QiLA0KICAgICAgICAgICAgICAgICAgICAgICAgIHhsYWIgPSAiQW5uw6llcyIsDQogICAgICAgICAgICAgICAgICAgICAgICAgeWxhYiA9ICJOb21icmUgZGUgVm95YWdldXJzIikgDQoNCg0KDQojcHLDqWRpY3Rpb24gZHUgbW9kw6hsZSBkZSBCdXlzIGJhbGxvdA0KbGluZXMoQW5uZWVzLHRlbmRhbmNlK3ByZWRpY3Rpb24yLGNvbD0iYmx1ZSIsbHdkPTIpDQoNCiNJbnRlcnZhbCBkZSBjb25maWFuY2UNCiBwb2x5Z29uKGMoQW5uZWVNb2lzTnVtZXJpY0Z1dHVyLHJldihBbm5lZU1vaXNOdW1lcmljRnV0dXIpKSwNCiBjKHRlbmRhbmNlMitQcmVkaWN0aW9uMy0xLjk2KnNxcnQodmFyKFJlc2lkdXNSZWdyZXNzaW9uMikpLA0KIHJldih0ZW5kYW5jZTIrUHJlZGljdGlvbjMrMS45NipzcXJ0KHZhcihSZXNpZHVzUmVncmVzc2lvbjIpKSkpLA0KIGNvbD0iY2FkZXRibHVlMSIsYm9yZGVyPU5BKQ0KIA0KICNQcmVkaWN0aW9uIGRlcyB2YWxldXJzDQogbGluZXMoQW5uZWVNb2lzTnVtZXJpY0Z1dHVyLHRlbmRhbmNlMitQcmVkaWN0aW9uMyxjb2w9ImJsdWUiLGx3ZD0yKQ0KIA0KIA0KIGxpbmVzKGRhdGFfdHNfdGVzdCxjb2w9ImJsYWNrIixsd2Q9MykNCmBgYA0KDQpBZmZpY2hhZ2UgZGUgbGEgcHLDqWRpY3Rpb24gc3VyIGxlcyA4IG1vaXMgZGUgMjAyMA0KDQpgYGB7cn0NCg0KQnV5c19iYWxsb3RfcGxvdCA8LSBwbG90KGRhdGFfdHNfdGVzdCwNCiAgICAgICAgICAgICAgICAgICAgICAgICBtYWluID0gIkFwcGxpY2F0aW9uIGR1IG1vZMOobGUgZGUgQnV5c19CYWxsb3QiLA0KICAgICAgICAgICAgICAgICAgICAgICAgIHhsYWIgPSAiQW5uw6llcyIsDQogICAgICAgICAgICAgICAgICAgICAgICAgeWxhYiA9ICJOb21icmUgZGUgVm95YWdldXJzIikgDQoNCg0KDQojcHLDqWRpY3Rpb24gZHUgbW9kw6hsZSBkZSBCdXlzIGJhbGxvdA0KbGluZXMoQW5uZWVzLHRlbmRhbmNlK3ByZWRpY3Rpb24yLGNvbD0iYmx1ZSIsbHdkPTIpDQoNCiNJbnRlcnZhbCBkZSBjb25maWFuY2UNCiBwb2x5Z29uKGMoQW5uZWVNb2lzTnVtZXJpY0Z1dHVyLHJldihBbm5lZU1vaXNOdW1lcmljRnV0dXIpKSwNCiBjKHRlbmRhbmNlMitQcmVkaWN0aW9uMy0xLjk2KnNxcnQodmFyKFJlc2lkdXNSZWdyZXNzaW9uMikpLA0KIHJldih0ZW5kYW5jZTIrUHJlZGljdGlvbjMrMS45NipzcXJ0KHZhcihSZXNpZHVzUmVncmVzc2lvbjIpKSkpLA0KIGNvbD0iY2FkZXRibHVlMSIsYm9yZGVyPU5BKQ0KIA0KICNQcmVkaWN0aW9uIGRlcyB2YWxldXJzDQogbGluZXMoQW5uZWVNb2lzTnVtZXJpY0Z1dHVyLHRlbmRhbmNlMitQcmVkaWN0aW9uMyxjb2w9ImJsdWUiLGx3ZD0yKQ0KIA0KIA0KIGxpbmVzKGRhdGFfdHNfdGVzdCxjb2w9ImJsYWNrIixsd2Q9MykNCmBgYA0KUHLDqXBhcmF0aW9uIERhdGFGcmFtZSBwb3VyIGFmZmljaGFnZSBnZ3Bsb3QNCmBgYHtyfQ0KRGF0YUFmZmljaGFnZUdHcGxvdCA9IGFzLmRhdGEuZnJhbWUoZGF0YV90cykNCkRhdGFBZmZpY2hhZ2VHR3Bsb3QkQW5uZWVzID0gYyhBbm5lZXMsIEFubmVlTW9pc051bWVyaWNGdXR1cikNCkRhdGFBZmZpY2hhZ2VHR3Bsb3QkQW5uZWVzUm91bmQgPSByb3VuZChEYXRhQWZmaWNoYWdlR0dwbG90JEFubmVlcykNCkRhdGFBZmZpY2hhZ2VHR3Bsb3QkUHJlZGljdGlvblRlbmRhbmNlID0gYyh0ZW5kYW5jZSAsdGVuZGFuY2UyKQ0KRGF0YUFmZmljaGFnZUdHcGxvdCRCdXlzQmFsb3RNb2RlbGUgPSBjKHRlbmRhbmNlK3ByZWRpY3Rpb24yLHRlbmRhbmNlMitQcmVkaWN0aW9uMyApDQoNCg0KYGBgDQoNCg0KDQpSZXByb2R1aXNvbnMgbGVzIGdyYXBoaXF1ZXMgYXZlYyBnZ3Bsb3QyIHBvdXIgdW4gcsOpc3VsdGF0IHBsdXMgcHJvZmVzc3Npb25uZWwuDQpgYGB7ciB3YXJuaW5nPUZBTFNFfQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShnZ3RoZW1lcykNCg0KcCA8LSBnZ3Bsb3QoZGF0YSA9RGF0YUFmZmljaGFnZUdHcGxvdCwgYWVzKHggPSBBbm5lZXMpICkgKyANCg0KICBnZW9tX2xpbmUoYWVzKHkgPSB0cmFmaWMgKSwgc2l6ZSA9IDAuOSwgYWxwaGEgPSAwLjcpKw0KDQogICNnZW9tX2xpbmUoYWVzKHkgPSBQcmVkaWN0aW9uVGVuZGFuY2UpLCBzaXplID0gMC42LCBhbHBoYSA9IDAuODUsbGluZXR5cGU9InR3b2Rhc2giICkrDQogIA0KICBnZW9tX2xpbmUoYWVzKHkgPSBCdXlzQmFsb3RNb2RlbGUpLCBzaXplID0gMS4yLCBhbHBoYSA9IDAuNiwgY29sb3IgPSAiYmx1ZSIpKw0KICBsYWJzKHRpdGxlID0gIkFwcGxpY2F0aW9uIGR1IG1vZMOobGUgZGUgQnV5c19CYWxsb3QiLA0KICAgICAgIHg9IkFubsOpZXMiLA0KICAgICAgICAgeT0gIk5vbWJyZSBkZSBWb3lhZ2V1cnMiKSsNCnRoZW1lX2ZpdmV0aGlydHllaWdodCgpKw0KICB0aGVtZShheGlzLnRpdGxlID0gZWxlbWVudF90ZXh0KCksIHRleHQgPSBlbGVtZW50X3RleHQoZmFtaWx5ID0gIlJ1YmlrIikpIA0KDQojc3VyIGwnYW5uw6llIDIwMTkNCnAyIDwtIGdncGxvdChkYXRhID1EYXRhQWZmaWNoYWdlR0dwbG90LCBhZXMoeCA9IEFubmVlcykgKSArIA0KICBnZW9tX2xpbmUoYWVzKHkgPSB0cmFmaWMgKSwgc2l6ZSA9IDEuMiwgYWxwaGEgPSAwLjcpKw0KICBnZW9tX2xpbmUoYWVzKHkgPSBCdXlzQmFsb3RNb2RlbGUpLCBzaXplID0gMS40LCBhbHBoYSA9IDAuNiwgY29sb3IgPSAiYmx1ZSIpKw0KdGhlbWVfZml2ZXRoaXJ0eWVpZ2h0KCkrDQogICB4bGltICgyMDE5LjAsIDIwMTkuNTgzKSArDQogIHlsaW0gKDQzNTAwMCwgNTIwMDAwKSANCg0KDQojQWpvdXQgem9vbSBzdXIgMjAxOQ0KcCArIA0KICBhbm5vdGF0aW9uX2N1c3RvbShnZ3Bsb3RHcm9iKHAyKSwgeG1pbiA9IDIwMTUsIHhtYXggPSAyMDIwLCB5bWluID0gNTAwMDAsIHltYXggPSAyODAwMDApICsNCiAgZ2VvbV9yZWN0KGFlcyh4bWluID0gMjAxNSwgeG1heCA9IDIwMjAsIHltaW4gPSA1MDAwMCwgeW1heCA9IDI4MDAwMCksIGNvbG9yPSdibGFjaycsIGxpbmV0eXBlPSdkYXNoZWQnLCBhbHBoYT0wKSANCg0KDQoNCmBgYA0KDQoNCg0KTm91cyBhdm9ucyByw6l1c3NpIMOgIGFqdXN0ZXIgdW5lIGRyb2l0ZSBkZSByw6lncmVzc2lvbi4gb24gcmVtYXJxdWUgcXVlIGxhDQpwcsOpZGljdGlvbiBzZW1ibGUgYmllbiBjb3JyZXNwb25kcmUgw6AgbGEgcsOpYWxpdMOpIHNpIG9uIGZhaXQgYWJzdHJhY3Rpb24NCmR1IGRlcm5pZXIgbW9pcyBvw7kgbGUgbm9tYnJlIGRlIHZveWFnZXVycyBhIGJpZW4gcGx1cyBjaHV0w6kgcXVlIGxhDQpwcsOpZGljdGlvbiBkdSBtb2TDqGxlIGRlIEJ1eXMtQmFsb3QuDQoNCkNvbXBhcm9ucyBhdmVjIHVuIGFqdXN0ZW1lbnQgbG9jYWwgcsOpYWxpc8OpIHBhciBsaXNzYWdlIG1veWVubmVzIG1vYmlsZXMuDQoNCiMjIENvbXBhcmFpc29uIGF2ZWMgbGVzIHZhbGV1cnMgb2JzZXJ2w6llcw0KDQoNCiMgTGlzc2FnZSBtb3llbm5lIG1vYmlsZQ0KDQojIyBEw6lmaW5pdGlvbg0KDQpNZXR0cmUgYmVsbGUgZm9ybXVsZSBlbiBsYXRleCBpY2kNCg0KIyMgQ2hvaXggTW95ZW5uZSBtb2JpbGVzDQoNCiMjIENvbnNlcnZhdGlvbiAmIEFubnVsYXRpb24NCg0KDQoNCg0KIyBMaXNzYWdlIGV4cG9uZW50aWVsbGUNCg0KIyMgTGlzc2FnZSBzaW1wbGUNCg0KYGBge3J9DQpmY3N0X3NlIDwtIHNlcyhkYXRhX3RzX3RyYWluLCBoID0gOCkNCnByaW50KHN1bW1hcnkoZmNzdF9zZSkpDQpjaGVja3Jlc2lkdWFscyhmY3N0X3NlKQ0KYGBgDQoNCmBgYHtyfQ0KcGxvdChmY3N0X3NlKQ0KbGluZXMoZGF0YV90c190ZXN0LCBjb2w9InJlZCIpDQoNCg0KZGZfc2UgPSBhcy5kYXRhLmZyYW1lKGZjc3Rfc2UpDQpwcmVkaWN0X3ZhbHVlX3NlIDwtIGRmX3NlJGBQb2ludCBGb3JlY2FzdGANCk1BUEUocHJlZGljdF92YWx1ZV9zZSwgZGF0YV90c190ZXN0KSoxMDANCmBgYA0KDQojIyBPcHRpbWlzYXRpb24gZHUgbW9kw6hsZQ0KDQpGaXQgRXhwb25lbnRpYWwgU21vb3RoaW5nIG1vZGVsIC0+IHRyb3V2ZSBsZSBtZWlsbGV1ciBsaXNzYWdlIGV4cG8NCg0KYGBge3J9DQpmaXRfZXRzIDwtIGV0cyhkYXRhX3RzX3RyYWluKSANCnByaW50KHN1bW1hcnkoZml0X2V0cykpDQpjaGVja3Jlc2lkdWFscyhmaXRfZXRzKQ0KDQoNCmBgYA0KDQpgYGB7cn0NCmZjc3RfZXRzIDwtIGZvcmVjYXN0KGZpdF9ldHMsIGg9OCkNCnBsb3QoZmNzdF9ldHMpDQpsaW5lcyhkYXRhX3RzX3Rlc3QsIGNvbD0icmVkIikNCg0KDQpkZl9ldHMgPSBhcy5kYXRhLmZyYW1lKGZjc3RfZXRzKQ0KcHJlZGljdF92YWx1ZV9ldHMgPSBkZl9ldHMkYFBvaW50IEZvcmVjYXN0YA0KTUFQRShwcmVkaWN0X3ZhbHVlX2V0cywgZGF0YV90c190ZXN0KSoxMDANCg0KYGBgDQoNCiMjIE1vZMOobGUgQXJpbWEgQXV0b21hdGlxdWUNCg0KYGBge3J9DQojIHJldG91cm5lIGxlcyBtZWlsbGV1cnMgcGFyYW3DqHRyZXMgDQojIGQ9MSBlbmxldmUgbGEgdGVuZGFuY2UNCiMgRD0xIGVubGV2ZSBsYSBzYWlzb25uYWxpdMOpIA0KIyA9PiBhdm9pciBkZXMgZG9ubsOpZXMgc3RhdGlvbm5haXJlcw0KIyB0cmFjZSA6IHZvaXIgbGVzIHLDqXN1bHRhdHMNCmZpdF9hcmltYSA8LSBhdXRvLmFyaW1hKGRhdGFfdHNfdHJhaW4sIGQ9MSwgRD0xLCBzdGVwd2lzZSA9IEZBTFNFLCBhcHByb3hpbWF0aW9uID0gRkFMU0UsIHRyYWNlPVRSVUUpDQpwcmludChzdW1tYXJ5KGZpdF9hcmltYSkpDQpjaGVja3Jlc2lkdWFscyhmaXRfYXJpbWEpDQpgYGANCg0KYGBge3J9DQpmY3N0X2FyaW1hIDwtIGZvcmVjYXN0KGZpdF9hcmltYSwgaD04KQ0KcGxvdChmY3N0X2FyaW1hKQ0KbGluZXMoZGF0YV90c190ZXN0LCBjb2w9J3JlZCcpDQoNCg0KZGZfYXJpbWEgPSBhcy5kYXRhLmZyYW1lKGZjc3RfYXJpbWEpDQpwcmVkaWN0X3ZhbHVlX2FyaW1hID0gZGZfYXJpbWEkYFBvaW50IEZvcmVjYXN0YA0KTUFQRShwcmVkaWN0X3ZhbHVlX2FyaW1hLCBkYXRhX3RzX3Rlc3QpKjEwMA0KYGBgDQoNCmBgYHtyfQ0KDQpgYGANCg0KYGBge3J9DQoNCg0KYGBgDQo=